AVL Tree
AVL tree is a height balance tree. If height of left and right sub trees of a binary search tree (BST) differs highly, then searching in that BST will be slow. Searching in lengthy tree takes more time than short tree.
To, remove this ineffiency of BST, AVL tree, a height balanced tree is developed. In AVL tree height of sub trees never differs more than 1, it can be -1, 0, or 1. Height of the AVL tree is adjusted at the time of inserting new node, if the insertion of new node voilates height factor (-1, 0 or 1) of the tree, then rotation of nodes is done to adjust the height factor of the tree.
class AVLNode {
int key, ht;
AVLNode left, right;
AVLNode(int d) {
key = d;
ht = 1;
}
}
class AVLTree {
AVLNode root;
// A utility function to get the ht of the tree
int getheight(AVLNode N) {
if (N == null)
return 0;
return N.ht;
}
int getMaxHeight(int x, int y) {
return (x > y) ? x : y;
}
AVLNode rightRotate(AVLNode b) {
AVLNode a = b.left;
AVLNode T2 = b.right;
// Perform rotation
a.right = b;
b.left = T2;
// Update hts
b.ht = getMaxHeight(getheight(b.left), getheight(b.right)) + 1;
a.ht = getMaxHeight(getheight(a.left), getheight(a.right)) + 1;
return a;
}
AVLNode leftRotate(AVLNode a) {
AVLNode b = a.right;
AVLNode T2 = b.left;
b.left = a;
a.right = T2;
a.ht = getMaxHeight(getheight(a.left), getheight(a.right)) + 1;
b.ht = getMaxHeight(getheight(b.left), getheight(b.right)) + 1;
return b;
}
int getBalance(AVLNode N) {
if (N == null)
return 0;
return getheight(N.left) - getheight(N.right);
}
AVLNode insert(AVLNode AVLNode, int key) {
if (AVLNode == null)
return (new AVLNode(key));
if (key < AVLNode.key)
AVLNode.left = insert(AVLNode.left, key);
else if (key > AVLNode.key)
AVLNode.right = insert(AVLNode.right, key);
else
return AVLNode;
AVLNode.ht = 1 + getMaxHeight(getheight(AVLNode.left),
getheight(AVLNode.right));
int bal = getBalance(AVLNode);
if (bal > 1 && key < AVLNode.left.key)
return rightRotate(AVLNode);
if (bal < -1 && key > AVLNode.right.key)
return leftRotate(AVLNode);
if (bal > 1 && key > AVLNode.left.key) {
AVLNode.left = leftRotate(AVLNode.left);
return rightRotate(AVLNode);
}
if (bal < -1 && key < AVLNode.right.key) {
AVLNode.right = rightRotate(AVLNode.right);
return leftRotate(AVLNode);
}
return AVLNode;
}
void preOrder(AVLNode AVLNode) {
if (AVLNode != null) {
System.out.print(AVLNode.key + " ");
preOrder(AVLNode.left);
preOrder(AVLNode.right);
}
}
void inOrder(AVLNode r){
if(r!=null){
inOrder(r.left);
System.out.println(r.key+ " ");
inOrder(r.right);
}
}
public static void main(String[] args) {
AVLTree tree = new AVLTree();
tree.root = tree.insert(tree.root, 10);
tree.root = tree.insert(tree.root, 20);
tree.root = tree.insert(tree.root, 30);
tree.root = tree.insert(tree.root, 40);
tree.root = tree.insert(tree.root, 50);
tree.root = tree.insert(tree.root, 25);
System.out.println("Preorder traversal" +
" of constructed tree is : ");
tree.preOrder(tree.root);
tree.inOrder(tree.root);
}
}